package com.code.test.dance;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * AB 两个二维数组，他们的一维数组都是 2 个数据，第一个作为 key，第二个作为值， 然后按照第一个数组的 kev 采 left ioin 的方式合并两个数组：
 * https://leetcode.cn/problems/combine-two-tables/solutions/3573/zu-he-liang-ge-biao-by-leetcode/
 */


/**
 * 二叉搜索树，找到 topk 的数据
 *
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.md
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 * <p>
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 提示：
 * <p>
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于
 * , n 是数组的大小。
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
 * 你可以按任意顺序返回答案。
 */
public class TopK {

    public static void main(String[] args) {
        int[] inputs = {1, 1, 1, 2, 2, 3, 4, 4, 4, 4, 4};
        List<Integer> s = topKFrequent(inputs, 2);
        System.out.println(s);

    }

    public static List<Integer> topKFrequent(int[] inputs, int k) {

        Map<Integer, Integer> countMap = new HashMap<>();

        for (int i = 0; i < inputs.length; i++) {
            int num = inputs[i];
            if (!countMap.containsKey(num)) {
                countMap.put(num, 0);
            }
            countMap.put(num, countMap.get(num) + 1);
        }

        List<Integer> ret = new ArrayList<>();

        //采用优先级队列，把元素逐渐入队，按照频率进行排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer t1, Integer t2) {
                return countMap.get(t1) - countMap.get(t2);
            }
        });

        /**
         * 小顶堆：父节点小于左右子节点
         * 大顶堆：父节点大于左右子节点
         * 这里要用小顶堆，因为如果用大顶堆，因为这队列里是高频，每次进来要把最大的弹出去，结果变成了求解最少频率
         * 小顶堆：队列里都是频率最少得，进来一个更高的，把最小的弹出去，求高频
         * 大顶堆：队列里都是频率最多的，进来一个更小的，把最大的弹出去，求低频
         */
        for (Integer num : countMap.keySet()) {
            if (queue.size() < k) {
                queue.add(num);
            } else if (countMap.get(num) > countMap.get(queue.peek())) {
                queue.remove();
                queue.add(num);
            }
        }
        while (!queue.isEmpty()) {
            ret.add(queue.poll());
        }

        return ret;
    }
}


